class Solution {
public:
    class Trie{
    public:
        unordered_map<char,Trie*> next;
        bool isEnd = false;
        Trie(){}
        void insert(string& s){
            reverse(s.begin(),s.end());
            Trie* cur = this;
            bool flag = false;
            for(char c : s){
                if(!cur->next.count(c)){
                    cur->next[c] = new Trie();
                    if(!flag){
                        flag = !flag;
                    }
                }
                cur = cur->next[c];
            }
            if(flag){
                cur->isEnd = true;
            }
        }
        
        int search(string& s){
            Trie* cur = this;
            for(char c : s){
                cur = cur->next[c];
            }
            if(cur->isEnd == false){
                return 0;
            }
            return s.size();
        }
        
    };
    int minimumLengthEncoding(vector<string>& words) {
        int ret = 0;
        sort(words.begin(),words.end(),[](auto& a,auto& b){
            if(a.size() == b.size()){
                return a < b;
            }
            return a.size() > b.size();
        });
        Trie* root = new Trie();
        for(string& s : words){
            root->insert(s);
        }
        
        for(int i = 0;i < words.size();i++){
            if(i > 0 && words[i] == words[i-1]){
                continue;
            }
            int path = root->search(words[i]);
            if(path > 0){
                ret += path + 1;
            }
        }
        return ret;
    }
};
